package day20210707;

import java.util.HashMap;
import java.util.Map;

/**
 * 1711. 大餐计数
 * 存hash表，再取出来匹配
 * @author lizy
 * @date 2021/07/07
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a  = {1,3,5,7,9};
        System.out.println(solution.countPairs(a));
    }
    public int countPairs(int[] deliciousness) {
        final int MOD = 1000000007;
        // 初始化菜品最大值
        int maxVal = 0;
        // 获取菜品最大值
        for (int val : deliciousness) {
            maxVal = Math.max(maxVal, val);
        }
        // 获取美味数理论最大值
        int maxSum = maxVal * 2;
        // 初始化对数
        int pairs = 0;
        // 初始化hash表
        Map<Integer, Integer> map = new HashMap<>(16);
        // 循环菜品数
        for (int val : deliciousness) {
            // 循环获取满足条件的菜品（2数之和，为2的幂等次方）
            for (int sum = 1; sum <= maxSum ; sum <<= 1) {
                // val为正整数
                if (sum - val>=0){
                    // 判断2数相加是否是2的幂等次
                    int count = map.getOrDefault(sum - val, 0);
                    // 获取对数
                    pairs = (pairs + count) % MOD;
                }
            }
            // 去重存入hash表
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return pairs;
    }
}
